1. Field of the Invention
The present invention relates to a technique for retrieving data, from a plural pieces of data to be retrieved, which matches or is similar to input retrieval data.
2. Description of the Related Art
A content addressable memory (CAM) is a memory which permits desired data to be retrieved from a plural pieces of stored data to be retrieved, based on the contents of input retrieval data.
FIG. 2 is a diagram showing the structure of a conventional content addressable memory. This content addressable memory has a plurality of word data memories WM.sub.1 to WM.sub.n respectively having memory cells MC.sub.1 to MC.sub.m the number of which corresponds to a number of bits of a word. The memory cells MC.sub.1 to MC.sub.m are respectively activated by word lines W.sub.1 to W.sub.n, thereby the data stored in the memory cells MC.sub.1 to MC.sub.m are readout respectively via bit lines B.sub.1 to B.sub.m. Such data read out from the memory cells MC.sub.1 to MC.sub.m via the bit lines B.sub.1 to B.sub.m are respectively supplied to a plurality of match detection circuits CC.sub.1 to CC.sub.n.
Each of the match detection circuits CC.sub.1 to CC.sub.n detects whether data on one of the bit lines B.sub.1 to B.sub.m matches data from a corresponding one of the memory cells MC.sub.1, to MC.sub.m, when a circuit operation signal line SC which is common to the entire words is in an active state. Each of the match detection circuits CC.sub.1 to CC.sub.n activates its corresponding one of match signal lines C.sub.1 to C.sub.n, when the data on the entire bit lines B.sub.1 to B.sub.m match the data from the memory cells MC.sub.1 MC.sub.m.
When retrieving data in the content addressable memory, the circuit operation signal line SC needs to be activated, in a state where the word lines W.sub.1 to W.sub.n are activated and retrieval data are output to the bit signal lines B.sub.1 to B.sub.m. In this case, if the data stored in the corresponding one of the word data memories WM.sub.1 to WM.sub.n, match the retrieval data, its corresponding match detection circuit C.sub.i (i=1, 2, , , n) is activated. By doing this, the data which are stored in the corresponding one of the word data memories WM.sub.1 to WM.sub.n and which match the retrieval data can be extracted.
The conventional content addressable memory includes the plurality of match detection circuits CC.sub.1 to CC.sub.n respectively corresponding to the word data memories WM.sub.1 to WM.sub.n. In this structure, the conventional content addressable memory can simultaneously detect the entire words whether any one of them corresponds to the retrieval data, resulting in retrieving the data at high speed. In this type of content addressable memory, the match detection circuits CC.sub.1 to CC.sub.n are operated all at the same time. In such circumstances, a problem occurs in that the content addressable memory consumes a lot of electric power. In order to solve such a problem, Unexamined Japanese Patent Application KOKAI Publication No. H9-180468 discloses a content addressable memory, in which data is retrieved in a limited range and a limited number of match detection circuits are activated.
FIG. 3 is a diagram showing the content addressable memory disclosed in Unexamined Japanese Patent Application KOKAI Publication No. H9-180468. This content addressable memory has a function for limiting a retrieval range for the following retrieval based on a result of the previous retrieval. In this function, a retrieval range is limited in a series of retrieval processes immediately upon reception of retrieval data, while outputting the word which has been extracted at the end as a retrieval result. In the series of retrieval processes, a retrieval process performed after the retrieval range is further limited is referred to as the "following retrieval", whereas a retrieval process performed before that is referred to as the "previous retrieval".
The content addressable memory has a memory cell array 2 storing data to be retrieved in the unit of words, an .OMEGA.-register 3A and a K-register 3b retaining the retrieval data, a match detection circuit array 4 including match detection circuits CC.sub.1 to CC.sub.10 independent from each word, a retrieval operation determination circuit 5 and a retrieval range limitation circuit 6. The memory cell array 2 stores as data to be retrieved a string table, for example, representing a dynamic dictionary and being formed using a data compression algorithm.
In the series of retrieval processes, after the previous retrieval, the content addressable memory processes a result of the previous retrieval and stores the processed data in the registers 3A and 3B. Before performing the following retrieval, in the content addressable memory, values (information specifying a retrieval range for the following retrieval based on the result of the previous retrieval) which are stored in the registers 3A and 3B are read, and a retrieval range is designated by the retrieval range limitation circuit 6. Accordingly, in the content addressable memory, a word which is in the first position within the retrieval range for the following retrieval can be designated using the result of the previous retrieval.
However, in order for the data stored in the memory cell array 2 to be retrieved based on the retrieval data, in the content addressable memory, the time for storing the values based on the result of the previous retrieval and the time for designating a retrieval range after reading the values stored in the registers 3A and 3B before the following retrieval are required. Therefore, in the content addressable memory, a problem arises in that the previous retrieval is switched over to the following retrieval with loss of time.
Such a content addressable memory requires the registers 3A and 3B storing the values of the previous retrieval and the circuit, for processing the values of the previous retrieval in the retrieval range limitation circuit 6. Obviously, the content addressable memory so needs a large space as to include such registers and circuit, and consumes a lot of electric power.
Furthermore, in the content addressable memory, of a plurality of obtained retrieval results which are assigned priorities, it is difficult to retrieve a retrieval result having the highest priority, since there is not means for designating priorities for the data. Therefore, in the content addressable memory, in a case where the plurality of retrieval results are obtained, the values to be stored in the registers 3A and 3B can not be specified, and the data can not be retrieved after setting a retrieval range.
Unexamined Japanese Patent Application KOKAI Publication No. H9-180469 discloses a content addressable memory in which a limited number of match detection circuits are activated. However, in such a content addressable memory, likewise that disclosed in Unexamined Japanese Patent Application KOKAI Publication No. H9-180468, the previous retrieval is switched over to the following retrieval with loss of time, and a register storing values of the previous retrieval is required, and further priorities for data pieces can not be specified when a plurality of retrieval results are obtained.